package cn.edu.thu.tsquality.core.algorithm.sequential.dependencies;


import javafx.util.Pair;

import java.util.Random;

public class Treap
{
    private static class Node
    {
        private static Random random;

        static
        {
            random = new Random();
        }

        private int prior;

        // value = interval[position], cost = keepTailCostMemory[position]
        private int position, value, realPosition;
        private int minPosition, maxPosition, minValue, minValueRealPosition;

        private Node lson, rson;

        public String toString()
        {
            return "["+position+","+value+"]  ["+ minPosition +","+ maxPosition +"]="+minValue+"  [realPos="+realPosition+"][minValueRealPosition="+minValueRealPosition+"][prior="+prior+"]";
        }

        private void setRandomPrior()
        {
            // prior = (int)((long)(prior) * 482711L % 2147483647);
            prior = random.nextInt();
        }

        private void update()
        {
            minValue = value;
            minPosition = maxPosition = position;
            minValueRealPosition = realPosition;
            if (lson != null)
            {
                if(lson.minValue < minValue)
                {
                    minValue = lson.minValue;
                    minValueRealPosition = lson.minValueRealPosition;
                }
                minPosition = Math.min(minPosition, lson.minPosition);
            }
            if (rson != null)
            {
                if(rson.minValue < minValue)
                {
                    minValue = rson.minValue;
                    minValueRealPosition = rson.minValueRealPosition;
                }
                maxPosition = Math.max(maxPosition, rson.maxPosition);
            }
        }

        @Deprecated
        public Node()
        {
            setRandomPrior();
            value = position = realPosition = 0;
            lson = rson = null;
            update();
        }

        public Node(int position, int value, int realPosition)
        {
            setRandomPrior();
            this.value = value;
            this.position = position;
            this.realPosition = realPosition;
            lson = rson = null;
            update();
        }

        public Node(int position, int value, int realPosition, Node lson, Node rson)
        {
            setRandomPrior();
            this.position = position;
            this.value =  value;
            this.realPosition = realPosition;
            this.lson = lson;
            this.rson = rson;
            update();
        }

        // rson.prior > prior
        private Node leftRotate()
        {
            Node rson = this.rson;
            this.rson = rson.lson;
            rson.lson = this;
            update();
            rson.update();
            return rson;
        }

        // lson.prior > prior
        private Node rightRotate()
        {
            Node lson = this.lson;
            this.lson = lson.rson;
            lson.rson = this;
            this.update();
            lson.update();
            return lson;
        }

    }

    private Node root;
    private static final int infInt = 0x3f3f3f3f;

    public Treap()
    {
        root = null;
    }

    private void print(Node root, int depth)
    {
        for(int i = 0; i < depth; i++)
            System.out.print("| ");
        if(root == null)
        {
            System.out.println("null");
            return;
        }
        System.out.println(root.toString());
        print(root.lson, depth+1);
        print(root.rson, depth+1);
    }

    public void print()
    {
        print(root, 0);
    }

    private int getDepth(Node root)
    {
        if(root == null)
            return 0;
        return Math.max(getDepth(root.lson), getDepth(root.rson)) + 1;
    }

    public int getDepth()
    {
        return getDepth(root);
    }


    private Node insert(Node root, Node node)
    {
        if(root == null)
            return node;

        if(node.position <= root.position)
            root.lson = insert(root.lson, node);
        else
            root.rson = insert(root.rson, node);

        if(root.lson!=null && root.lson.prior > root.prior)
            return root.rightRotate();

        if(root.rson!=null && root.rson.prior > root.prior)
            return root.leftRotate();

        root.update();
        return root;
    }

    public void insert(int position, int value, int realPosition)
    {
        Node node = new Node(position, value, realPosition);
        root = insert(root, node);
    }


    // 返回 <最小值, 此最小值的那个真实下标>
    private Pair<Integer, Integer> query(Node node, int l, int r)
    {
        if (node == null || l > node.maxPosition || r < node.minPosition)
            return new Pair<>(infInt, -1);

        if (l <= node.minPosition && r >= node.maxPosition)
            return new Pair<>(node.minValue, node.minValueRealPosition);

        if (node.position < l)
            return query(node.rson, l, r);

        if (node.position > r)
            return query(node.lson, l, r);

        Pair<Integer, Integer> lson = query(node.lson, l, r);
        Pair<Integer, Integer> rson = query(node.rson, l, r);
        if (lson.getKey() < rson.getKey())
        {
            if (lson.getKey() < node.value)
                return lson;
            else
                return new Pair<>(node.value, node.realPosition);
        }
        else
        {
            if (rson.getKey() < node.value)
                return rson;
            else
                return new Pair<>(node.value, node.realPosition);
        }
    }

    public Pair<Integer, Integer> query(int l, int r)
    {
        return query(root, l, r);
    }
}
